/*
 * Queue.h
 *
 *  Created on: May 3, 2013
 *      Author: Lucifer
 */

#ifndef __BFX_QUEUE_H__
#define __BFX_QUEUE_H__

namespace BFX
{

/**
 * Represents a first-in, first-out queue of elements. Internally it is implemented as a
 * circular buffer, so Enqueue can be O(n).  Dequeue is O(1).
 */
template<class T>
class Queue
{
	typedef	T	TYPE;
	typedef	const T&	ARG_TYPE;
public:

	/**
	 * Creates a queue with room for capacity objects.
	 *
	 * @param nCapacity The initial number of elements that the Queue can contain. The default value is (32).
	 */
	Queue(int nCapacity = 32)
	{
		BFX_REQUIRE1(nCapacity >= 0, "Non-negative number required.");

		m_pArray = NULL;
		m_nAllocSize = 0;
		m_nSize = 0;
		m_iHead = 0;
		m_iTail = 0;

		if (nCapacity > 0)
			Capacity(nCapacity);
	}

	Queue(const Queue& src)
	{
		m_pArray = NULL;
		m_nAllocSize = 0;
		m_nSize = 0;
		m_iHead = 0;
		m_iTail = 0;

		(*this) = src;
	}

	/**
	 * Destroys the queue.
	 */
	virtual ~Queue()
	{
		Clear();
		if (m_pArray != NULL)
			delete[] (BYTE*)m_pArray;
	}

	Queue& operator=(const Queue& src)
	{
		Clear();

		int nSrcLen = src.GetSize();
		Capacity(nSrcLen);
		for (int i = 0; i < nSrcLen; i ++)
		{
			ARG_TYPE element = src.GetAt(i);
			Enqueue(element);
		}
		return (*this);
	}

	/**
	 * Adds item to the tail of the queue.
	 * @param element The object to add to the queue.
	 */
	void Enqueue(ARG_TYPE element)
	{
		if (m_nSize == m_nAllocSize)
			Capacity(m_nAllocSize + 1);

		m_pArray[m_iTail] = element;
		m_iTail = (m_iTail + 1) % m_nAllocSize;
		m_nSize ++;
	}

	/**
	 * Removes the object at the head of the queue and returns it. If the queue is empty will rises an contract exception.
	 * @return The object that is removed from the beginning of the queue.
	 */
	TYPE Dequeue()
	{
		BFX_REQUIRE1(GetSize() > 0, "Queue empty");

		TYPE result = m_pArray[m_iHead];
		(m_pArray + m_iHead)->~TYPE();
		m_nSize --;
		return result;
	}

	/**
	 * Returns the object at the head of the queue. The object remains in the queue. If the queue is empty will rises an contract exception.
	 * @return The object at the beginning of the queue
	 */
	ARG_TYPE Peek()
	{
		BFX_REQUIRE1(GetSize() > 0, "Queue empty");

		return m_pArray[m_iHead];
	}

	/**
	 * Determines whether an element is in the queue.
	 * @param element The element to locate in the queue.
	 * @return true if element is found in the queue; otherwise, false.
	 */
	bool Contains(ARG_TYPE element) const
	{
		int iIndex = m_iHead;
		int nSize = m_nSize;
		while (nSize-- > 0)
		{
			if (m_pArray[iIndex] == element)
				return true;
			iIndex = (iIndex + 1 % m_nAllocSize);
		}
		return false;
	}

	/**
	 * Gets the value indicates whether this queue contains no elements.
	 * @return True if the queue is empty; otherwise false.
	 */
	bool IsEmpty() const
	{
		return (GetSize() == 0);
	}

	/**
	 * Gets the number of elements contained in the queue.
	 * @return
	 */
	int GetSize() const
	{
		return m_nSize;
	}

	/**
	 * Gets the element of given index.
	 * @param iIndex The index of the element to retrieve.
	 * @return The object at the given index of the queue.
	 */
	ARG_TYPE GetAt(int iIndex) const
	{
		BFX_REQUIRE1(GetSize() > iIndex, "Queue empty");

		return m_pArray[(m_iHead + iIndex) % m_nAllocSize];
	}

	/**
	 * Removes all elements from the queue.
	 */
	void Clear()
	{
		if (m_iHead < m_iTail)
		{
			for (int i = 0; i < m_nSize; i++)
				(m_pArray + m_iHead + i)->~TYPE();
		}
		else
		{
			for (int i = 0; i < m_nAllocSize - m_iHead; i++)
				(m_pArray + m_iHead + i)->~TYPE();
			for (int j = 0; j < m_iTail; j++)
				(m_pArray + j)->~TYPE();
		}
		m_iHead = 0;
		m_iTail = 0;
		m_nSize = 0;
	}

protected:

	// Grows or shrinks the buffer to hold capacity objects. nCapacity must be >= m_nSize.
	void Capacity(int nCapacity)
	{
		if (nCapacity <= m_nSize)
			return;

		int nAllocSize = 1;
		while ((nAllocSize <<= 1) < nCapacity)
			;
		TYPE* pNewArray = (TYPE*) new BYTE[nAllocSize * sizeof(TYPE)];
		if (m_nSize > 0)
		{
			// copy exist elements to new block.
			if (m_iHead < m_iTail)
			{
				memmove(pNewArray, m_pArray + m_iHead, m_nSize * sizeof(TYPE));
			}
			else
			{
				memmove(pNewArray, m_pArray + m_iHead, (m_nAllocSize - m_iHead) * sizeof(TYPE));
				memmove(pNewArray + (m_nAllocSize - m_iHead), m_pArray, m_iTail * sizeof(TYPE));
			}
		}
		// construct remaining elements
		for (int i = 0; i < nAllocSize - m_nSize; i++)
			::new ((void*) (pNewArray + m_nSize + i)) TYPE;

		if (m_pArray)
			delete[] (BYTE*) m_pArray;
		m_pArray = pNewArray;
		m_nAllocSize = nAllocSize;

		m_iHead = 0;
		m_iTail = (m_nSize == nCapacity) ? 0 : m_nSize;
	}

protected:
	TYPE*	m_pArray;
	int		m_nAllocSize;

	int		m_nSize;	// number of elements.
	int		m_iHead;	// first index of valid element in the queue
	int		m_iTail;	// last index of valid element in the queue
};

} /* namespace BFX */

#endif /* __BFX_QUEUE_H__ */
